package kyssion.leetcode.num51_100;


import java.util.ArrayList;
import java.util.List;

public class code51_N皇后 {
    public static void main(String[] args) {
        List<List<String>> lists = new code51_N皇后().solveNQueens(5);
        for (List<String> i : lists) {
            for(String s:i){
                System.out.println(s);
            }
            System.out.println();
        }
    }

    /**
     * 解法一 基本回朔算法
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        char[][] item = new char[n][n];
        init(item);
        boolean[] col = new boolean[n];
        boolean[] row = new boolean[n];
        boolean[] leftDiag = new boolean[2*n];
        boolean[] rightDiag = new boolean[2*n];
        List<List<String>> lists = new ArrayList<>();
        ans(n, 0, item, col, row, leftDiag, rightDiag, lists);
        return lists;
    }

    public void init(char[][] item) {
        for (int a = 0; a < item.length; a++) {
            for (int b = 0; b < item[a].length; b++) {
                item[a][b] = '.';
            }
        }
    }

    public void ans(int n, int indexLine, char[][] item,
                    boolean[] col, boolean[] row, boolean[] leftDiga, boolean[] rightDiag,
                    List<List<String>> lists) {
        if (indexLine >= n) {
            List<String> iii = new ArrayList<>();
            for (int a = 0; a < n; a++) {
                iii.add(new String(item[a]));
            }
            lists.add(iii);
        }
        for (int a = 0; a < n; a++) {
            if (!col[a] && !row[a] && !leftDiga[n-a+indexLine] && !rightDiag[a+indexLine]) {
                col[a] = row[a] = leftDiga[n-a+indexLine] = rightDiag[a+indexLine] = true;
                item[indexLine][a] = 'Q';
                ans(n, indexLine + 1, item, col, row, leftDiga, rightDiag, lists);
                item[indexLine][a] = '.';
                col[a] = row[a] = leftDiga[n-a+indexLine] = rightDiag[a+indexLine] = false;
            }
        }
    }
}
